
public class TwoLinkBinTree<T> {

    public static void main(String[] args) {
        TwoLinkBinTree<Integer> ints = new TwoLinkBinTree<>();

        ints.insert(45);
        ints.insert(21);
        ints.insert(12);
        ints.insert(13);
        ints.insert(18);
        ints.insert(53);
        ints.insert(77);
        ints.insert(243);
        ints.insert(32);
        ints.insert(64);


        Node node = ints.findNode(ints.root, 53);
        if (node != null) {
            System.out.println("true");
        } else {
            System.out.println("false");
        }

        System.out.println("size="+ints.getSize(ints.root));

        ints.getLeaf(ints.root);

    }

    public boolean insert(int data) {
        Node newNode = new Node(data);
        if(root == null){//当前树为空树，没有任何节点
            root = newNode;
            return true;
        }else{
            Node current = root;
            Node parentNode = null;
            while(current != null){
                parentNode = current;
                if((int)current.data > data){//当前值比插入值大，搜索左子节点
                    current = current.left;
                    if(current == null){//左子节点为空，直接将新值插入到该节点
                        parentNode.left= newNode;
                        return true;
                    }
                }else{
                    current = current.right;
                    if(current == null){//右子节点为空，直接将新值插入到该节点
                        parentNode.right = newNode;
                        return true;
                    }
                }
            }
        }
        return false;
    }


    private Node root;

    public TwoLinkBinTree() {
    }

    public TwoLinkBinTree(T data) {
        root = new Node(data);
    }


    public boolean isEmpty() {
        return root.data == null;
    }

    //获取根节点
    public Node getRoot() {
        if (isEmpty()) {
            throw new RuntimeException("树为空");
        }
        return root;
    }

    //set root
    public void setRootData(T data) {
        if (root != null && root.data == null) {
            root.data = data;
        } else {
            throw new RuntimeException("该根节点已有数据");
        }
    }


    //get root deep
    public int getDeep() {
        return deep(root);
    }

    //get node deep
    private int deep(Node node) {
        if (node == null) {
            return 0;
        }
        if (node.left == null && node.right == null) {
            return 1;
        } else {
            int leftDeep = deep(node.left);
            int rightDeep = deep(node.right);

            //get max
            int max = leftDeep > rightDeep ? leftDeep : rightDeep;
            return max + 1;
        }
    }


    // 获取树大小
    private int getSize(Node node) {
        if (node == null) {
            return 0;
        } else {
            return 1 + getSize(node.left) + getSize(node.right);
        }
    }


    public Node findNode(Node node, T data) {
        if (node == null) {
            return null;
        } else if (node.data == data) {
            return node;
        }
        Node leftNode = findNode(node.left, data);
        if (null != leftNode)
            return leftNode;
        Node rightNode = findNode(node.right, data);
        if (null != rightNode)
            return rightNode;
        return null;
    }


    //获得叶子数
    public void getLeaf(Node node) {
        if (node == null) {
            return;
        }
        if (node.left == null && node.right == null) {
            System.out.println("Leaf node: " + node.data);
        } else {
            getLeaf(node.left);
            getLeaf(node.right);
        }
    }



public static class Node {
    Object data;
    Node left;
    Node right;

    public Node() {

    }

    public Node(Object data) {
        this.data = data;
        this.left = null;
        this.right = null;
    }

    public Node(Object data, Node left, Node right) {
        this.data = data;
        this.left = left;
        this.right = right;
    }
}
}